/*
接收一个正整数n，输出由1~n组成的数的全部组合。
 */

package com.yuan.algorithms.Algorithm_2;

import java.util.Scanner;
public class 递归_全排列 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] x = new int[n];  //存储排列
            int[] mark = new int[n+1];  //标记元素
            printPermutation(n,0,x,mark);
        }
    }
    /**
     * 打印1~n的全排列
     * 
     * @param n  全排列的元素
     * @param current  当前填数的位置
     * @param x  存储排列的数组
     * @param mark  标记该数是否已使用
     */
    public static void printPermutation(int n, int current, int[] x, int[] mark){
        if (current==n) {
            for (int i = 0; i < n; i++) {
                System.out.print(x[i]);
            }
            System.out.println();
        } else {
            for (int i = 1; i <= n; i++) {
                if (mark[i] == 0) {
                    x[current] = i;//填充未使用的数i
                    mark[i]++;//标记i已使用
                    printPermutation(n,current+1,x,mark);//递归，进入下一个位置的填数
                    mark[i]--;//取消标记
                }
            }
        }
        
    }
}
